package com.isaiah.graph.adjacencylist;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Title: 基于邻接表的无向图实现
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/6/515:54
 */
public class Graph {
    /** 顶点数目 */
    private final int V;

    /** 边的数目 */
    private int E;

    /** 邻接表 */
    private LinkedList<Integer>[] adj;

    public Graph(int v) {
        // 初始化顶点数量
        V = v;
        // 初始化边的数量
        E = 0;
        // 初始化邻接表
        this.adj = new LinkedList[v];
        for (int i = 0;i < adj.length; i++){
            adj[i] = new LinkedList<Integer>();
        }
    }

    /**
     * 获取顶点数目
     * @return
     */
    public int V(){
        return V;
    }

    /**
     * 获取边的数目
     * @return
     */
    public int E(){
        return E;
    }

    /**
     * 向图中添加一条边(v,w)
     * @param v
     * @param w
     */
    public void addEage(int v, int w){
        // 在无向图中，边可说是从v到w,也可以说是从w到v， 因此，需要让w出现在v的邻接表中，并且还要让v出现在w的邻接表中
        adj[v].addFirst(w);
        adj[w].addFirst(v);
        // 维护边数
        E++;
    }

    /**
     * 获取和顶点v相邻的所有顶点集合
     * @param v
     * @return
     */
    public LinkedList<Integer> addj(int v){
        return adj[v];
    }
}
